package com.zang.array;

/**
 * 寻找重复数
 * @author ZVerify
 * @since 2022/10/18 21:18
 * @see <a href="https://leetcode.cn/problems/find-the-duplicate-number/submissions/">...</a>
 **/
public class 寻找重复数 {

    // 模拟链表成环
    public int findDuplicate(int[] nums){

        int fast = 0;
        int slow = 0;

        while (true){

            fast = nums[nums[fast]];
            slow = nums[slow];
           if (fast==slow) break;
        }
        slow = 0;
        while (true){

            fast = nums[fast];
            slow = nums[slow];
            if (fast==slow) break;
        }
        return fast;
    }
}
